package com.algorithm.cn.recursion;
/**
 * 
 * @author wangzonghui
 * @date 2021-01-10 21:16:56
 * @Description: 递归解决迷宫问题
 */
public class MiGong {

	public static void main(String[] args) {
		//创建地图
		int [] [] map=new int [8][7];
		//使用1表示墙
		for(int i=0;i<7;i++) {
			map[0][i]=1;
			map[7][i]=1;
		}
		
		for(int i=0;i<8;i++) {
			map[i][0]=1;
			map[i][6]=1;
		}
		
		//设置挡板
		map[3][1]=1;
		map[3][2]=1;
		
		//输出地图
		for(int i=0;i<8;i++) {
			for(int j=0;j<7;j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
		
		//使用递归回溯给小球找路
		setWay(map,1,1);
		
		//输出新的地图，小球走过的路
		System.out.println("小球找到路");
		for(int i=0;i<8;i++) {
			for(int j=0;j<7;j++) {
				System.out.print(map[i][j]+" ");
			}
			System.out.println();
		}
	}

	/**
	 * 使用递归回溯给小球找路
	 * 约定：map[i][j]=0表示为走过，1表示墙，2表示通路，3走过但不通
	 * 走迷宫时，确定策略（方法），下 ->右 ->上 ->左，如果该点走不通，在回溯。
	 * @param map 地图
	 * @param i 开始x
	 * @param j 开始y
	 * @return 通路 true  否则返回false 小球找到map[6][5]表示通路
	 */
	public static boolean setWay(int[][]map,int i,int j) {
		if(map[6][5]==2) {  //通路ok
			return true;
		}else {
			
			if(map[i][j]==0) {   //当前点为0 ，未走过
				//按策略走 下 ->右 ->上 ->左
				map[i][j] =2;  //假定能走通
				if(setWay(map, i+1, j)) {  //向下走
					return true;
					
				}else if(setWay(map, i, j+1)) {  //向右
					return true;
					
				}else if(setWay(map, i-1, j)) {  //向上
					
					return true;
				}else if(setWay(map, i, j-1)) {  //向左
					return true;
					
				}else {  //说明该点走不通，是思路
					map[i][j]=3;
					return false;
				}
				
			}else {  //map[i][j] 1墙 2 可以走 3 思路
				return false;
			}
		}
	}
}
